package com.maishi.programmer.array;

/**
 * Created by brossdong on 2018/3/14.
 * 旋转数组的最小数字
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，
 * 输出旋转数组的最小元素。例如数 组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为 1.
 * 注意一个特殊情况:{1,0,1,1,1,1} {1,1,1,1,1,0,1}这样只能采用顺序查找
 */
public class TestArrays8 {

    /*public static Integer findMin (int[] arrays) {

        if (arrays == null) return null;
        //定义两个指针p,q
        int leftp = 0;
        int rightq = arrays.length - 1;

        int mid = 0;
        while (arrays[leftp] >= arrays[rightq]) {
            if (rightq - leftp <= 1) {
                mid = rightq;
                break;
            }

            mid = (leftp + rightq) / 2;

            //如果中间与两边数字都相同
            if (arrays[leftp] == arrays[rightq] && arrays[leftp] == arrays[mid]) {
                if (arrays[leftp+1] != arrays[rightq - 1]) {
                    mid = arrays[leftp + 1] < arrays[rightq - 1] ? arrays[leftp + 1] : arrays[rightq - 1];
                    break;
                } else {
                    leftp++;
                    rightq--;
                }
            }else {
                if (arrays[mid] >= arrays[leftp]) {
                    leftp = mid;
                }else {
                    if (arrays[mid] <= arrays[rightq]) {
                        rightq = mid;
                    }
                }
            }
        }

        return arrays[mid];
    }*/
    public int minNumberInRotateArray(int[] array) {
        if (array == null || array.length == 0)
            return 0;
        int low = 0;
        int high = array.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            //System.out.println(mid);
            if (array[mid] > array[high]) {
                low = mid + 1;
                // high = high - 1;可以避免low，high,mid相等的找不到最小值情况。
                // int[] array={1,0,1,1,1};
            } else if (array[mid] == array[high]) {
                high = high - 1;
            } else {
                high = mid;
            }
        }
        return array[low];
    }

    public static void main(String[] args) {
        TestArrays8 p8= new TestArrays8();
        //int[] array={1,1,1,2,0};
        int[] array={4,5,6,2,3};
        //int[] array={1,0,1,1,1};
        //int[] array = {0,1,1,1,1};
        System.out.println(p8.minNumberInRotateArray(array));
    }

}
